
package progentiere.knapsackprb;

import java.util.Collections;


public class SpecializedBrandAndBound extends Algorithm
{
    static double EPSILON = 0.0000001;
    static double MAXTIME = 5;
    
    @Override
    Solution solve(KnapSackProblem problem) 
    {
        Collections.sort(problem.getItems());
        
        long start = System.nanoTime();
        int i = 0;
        int n = problem.getNbItems() - 1;
        double c = problem.getCapacity();
        double z = 0;
        double boundLow = 0;
        double boundUpp = 0;
        Solution incSol = new Solution(problem.getNbItems());
        Solution optSol = new Solution(problem.getNbItems());        
        
        while(true)
        {
            boundUpp = greedyRelaxFromI(problem, incSol, i + 1).getProfit(problem);
            if((double)(System.nanoTime() - start) / 1000000000d >= MAXTIME)
            {
                return optSol;
            }
            
            if(boundUpp <= boundLow + EPSILON)
            {
                if(i == n + 1)
                {
                    if (incSol.getContent()[n] == 1)
                    {
                        z -= problem.getItems().get(n).getProfit();
                        c += problem.getItems().get(n).getWeight();
                        incSol.getContent()[n] = 0;
                    }
                    i -= 2;
                }
                while(incSol.getContent()[i] == 0)
                {
                    i--;
                    if (i == -1)
                    {
                        optSol.setOptimal();
                        return optSol;
                    }                        
                }
                incSol.getContent()[i] = 0;
                z -= problem.getItems().get(i).getProfit();
                c += problem.getItems().get(i).getWeight();
                i++;
            }
            else 
            {
                while(i <= n && c >= problem.getItems().get(i).getWeight())
                {
                    incSol.getContent()[i] = 1;
                    z += problem.getItems().get(i).getProfit();
                    c -= problem.getItems().get(i).getWeight();
                    i++;
                }
                if (i < n + 1)
                {
                    incSol.getContent()[i] = 0;
                    i++;
                }                
                else if (i == n + 1)
                {           
                    if (z > boundLow)
                    {   
                        optSol = new Solution(incSol);
                        boundLow = z;
                    }
                }
            }
        }
    }

    private Solution greedyRelaxFromI(KnapSackProblem problem, Solution incumbent, int iObject) 
    {        
        Solution solution = new Solution(incumbent);
        
        double remainingCapacity = problem.getCapacity() - solution.getWeight(problem);
        
        for(int i = iObject ; i < problem.getNbItems() ; i++)
        {
            if(problem.getItems().get(i).getWeight() <= remainingCapacity)
            {
                solution.getContent()[i] = 1;
                remainingCapacity -= problem.getItems().get(i).getWeight();
            }
            else 
            {
                if (remainingCapacity > 0)
                {
                    solution.getContent()[i] = remainingCapacity / problem.getItems().get(i).getWeight();
                    remainingCapacity = 0;
                }
                else 
                {
                    solution.getContent()[i] = 0;
                }
            }
        }
        
        return solution;
    }
}
